package org.example.dynamic_planning;

import java.util.Arrays;

public class Different_subsequences {
    public static int len = 0;
    public static int res = 0;
    public static void main(String[] args) {
        //不同的子序列

        //给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
        String s = "rabbbit";
        String t = "rabbit";
        int i = numDistinct(s, t);
        System.out.println(i);
    }

    //动态规划
    public static int numDistinct(String s, String t) {
        int[][] dp = new int[t.length() + 1][s.length() + 1];
        for (int i = 1; i <= t.length(); i++) {
            for (int j = 1; j <= s.length(); j++) {
                if (t.charAt(i-1) == s.charAt(j-1) && i == 1){
                    dp[i][j] = dp[i][j-1] + 1;
                } else if (t.charAt(i - 1) == s.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                } else {
                    dp[i][j] = dp[i][j-1];
                }

            }
            System.out.println(Arrays.deepToString(dp));
        }
        return dp[t.length()][s.length()];
    }

    //回溯算法,超时
    public static int numDistinct2(String s, String t) {
        getNumber(s,t,0,0);
        return res;
    }
    public static void getNumber(String s, String t,int pre,int last){
        if (len == t.length()){
            res++;
            return;
        }
        for (int i = pre; i < t.length(); i++) {
            for (int j = last; j < s.length(); j++) {
                if (t.charAt(i) == s.charAt(j)){
                    len++;
                    pre = i+1;
                    last = j+1;
                    getNumber(s,t,pre,last);
                    len--;
                }
            }
        }

    }
}
